# coding=utf-8


class SortColors:
    def sortColors(self, nums):
        n = len(nums)
        p0 = p1 = 0
        for i in range(n):
            if nums[i] == 1:
                nums[i], nums[p1] = nums[p1], nums[i]
                p1 += 1
            elif nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                if p0 < p1:
                    nums[i], nums[p1] = nums[p1], nums[i]
                p0 += 1
                p1 += 1

    # 方法2：
    def sortColors2(self, nums):
        left, right = 0, len(nums)-1
        index = 0
        while (index <= right):
            if (nums[index] == 0):
                self.swap(nums, index,left)
                index = index + 1
                left = left + 1
            elif (nums[index] == 2):
                self.swap(nums, index, right)
                right = right - 1
            else:
                index = index + 1

    def swap(self, nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp


if __name__ == '__main__':
    nums = [2, 0, 2, 1, 1, 0]

    sortColors = SortColors()
    sortColors.sortColors2(nums)
    print nums
